﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace CCodeTreeLib
{
    public static class KnuthMorrisPratt
    {
        public static long ReadTo(byte[] pattern, byte[] data, int offset, Stream stream)
        {
            var mStream = new MemoryStream(data);
            mStream.Position = offset;
            return ReadTo(pattern, mStream, stream);
        }

        public static long ReadTo(byte[] pattern, Stream stream, Stream outStream)
        {
            //I will have to implement some sort of linear string matching algorithm.
            //Knuth-Morris-Pratt algorithm:
            int[] f = KmpFailureFunction(pattern);
            int j = 0;
            int tmp = stream.ReadByte();
            if (tmp == -1)
                return tmp;//end of stream
            byte t = (byte)tmp;
            if (outStream != null) outStream.WriteByte(t);
            while (stream.Position <= stream.Length)
            {
                if (pattern[j] == t)
                {
                    if (j == pattern.Length - 1)//see if we have a match
                        return stream.Position - pattern.Length;//i-m+1
                    tmp = stream.ReadByte();
                    if (tmp < 0)
                        return tmp;//end of stream
                    t = (byte)tmp;
                    if (outStream != null) outStream.WriteByte(t);
                    j++;
                }
                else if (j > 0)
                {//move forward in the pattern
                    j = f[j - 1];
                }
                else
                {
                    tmp = stream.ReadByte();
                    if (tmp < 0)
                        return tmp;//end of stream
                    t = (byte)tmp;
                    if (outStream != null) outStream.WriteByte(t);
                }
            }
            return -1;//There is no matching substring
        }

        private static int[] KmpFailureFunction(byte[] pattern)
        {
            int i = 1;
            int j = 0;
            int[] f = new int[pattern.Length];
            if (f.Length > 0)
                f[0] = 0;
            while (i < pattern.Length)
            {
                if (pattern[j] == pattern[i])
                {
                    //we have matched j+1 characters
                    f[i] = j + 1;
                    i++;
                    j++;
                }
                else if (j > 0)
                {
                    //j indexes just after a prefic of P that must match
                    j = f[j - 1];
                }
                else
                {
                    //no match
                    f[i] = 0;
                    i++;
                }
            }
            return f;
        }
    }
}
